/*
 * Author: Wang Hsutung
 * Date: 2015/11/15
 * Locale: Wuhan, Hubei
 * Email: hsu[AT]whu.edu.cn
 */

#include <iostream>
#include <string>
#include <deque>

using std::cin;
using std::cout;
using std::endl;

struct node {
    char ch;
    node *left;
    node *right;

    node(char c, node *l = NULL, node *r = NULL) :
        ch(c), left(l), right(l) {}

    static void print(node *p, std::string prefix = "")
    {
        if (!p) {
            cout << "(null)" << endl;
            return;
        }
        cout << p->ch << endl;

        if (p->left || p->right) {
            cout << prefix << "├── ";
            print(p->left,  prefix + "│   ");
            cout << prefix << "└── ";
            print(p->right, prefix + "    ");
        }
    }

};

struct binTree {
    node *root;

    binTree(): root(NULL) {}

    void print(void)
    {
        node::print(root);
    }

    void construct(const char *cstr)
    {
        if (cstr == NULL || cstr[0] == '\0')
            return;
        std::string str(cstr);
        std::deque<node *> que;

        std::string::iterator it = str.begin();
        root = new node(*it++);
        que.push_back(root);

        while (it != str.end()) {
            node *p = que.front();
            que.pop_front();
            p->left = new node(*it++);
            que.push_back(p->left);

            if (it != str.end()) {
                p->right = new node(*it++);
                que.push_back(p->right);
            } else {
                break;
            }
        }
    }
};

int main(int argc, char *argv[])
{
    binTree tree;
    const char arr[] = "ABCDEFGHIJKL";

    cout << "\nComplete-Binary-Tree for array [" << arr
         << "] with non-recursive implementation: \n" << endl;

    tree.construct(arr);
    tree.print();

    return 0;
}

